package experiment5;

import java.nio.file.Path;
import java.util.*;

public class PrimeNumber {
    Random randomNumber;

    PrimeNumber(Random random) {
        randomNumber = random;
    }

    boolean prime(long n) {
        if (n == 1) {
            return false;
        }
        if (n == 2 || n == 3) {
            return true;
        }

        long a;
        a = randomNumber.nextLong() % (n -3)+ 2;
        Pair.result = 1;
        Pair.composite = false;
        power(a, n - 1, n);
        if (Pair.composite || Pair.result != 1) {
            return false;
        } else {
            return true;
        }
    }

    boolean primeMC(long n) {
        if (n == 1) {
            return false;
        }
        if (n == 2 || n == 3) {
            return true;
        }

        long a;

        Pair.result = 1;
        Pair.composite = false;

        for (int i = 0; i < 1000; i++) {
            a = randomNumber.nextLong() % (n-3) + 2;
            power(a, n - 1, n);
            if (Pair.composite || Pair.result != 1) {
                return false;
            }
        }
        return true;

    }


    void power(long a, long p, long n) {
        if (p == 0) {
            Pair.result = 1;
        } else {
            power(a, p / 2, n);
            long x = Pair.result;
            Pair.result = (x * x) % n;
            if ((Pair.result == 1) && (x != 1) && (Pair.result != n - 1)) {
                Pair.composite = true;
            }
            if ((p % 2) == 1) {
                Pair.result = (Pair.result * a) % n;
            }
//            if (Pair.composite || Pair.result != 1) {
//                System.out.println(a + ":" + p + ":" + n + ":" + Pair.result + ":" + Pair.composite);
//
//            } else {
//                System.out.println(a + ":" + p + ":" + n + ":" + Pair.result + ":" + Pair.composite);
//
//            }

        }

    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        PrimeNumber randomNumber = new PrimeNumber(new RandomNumber());
        PrimeNumber random = new PrimeNumber(new Random());

        long n;
        while ((n = scanner.nextLong()) != -1) {
            System.out.println("primeNumber:");
            System.out.println((randomNumber.prime(n)) ? "是素数" : "不是素数");
            System.out.println((randomNumber.primeMC(n)) ? "是素数" : "不是素数");
            System.out.println("random:");
            System.out.println(random.prime(n) ? "是素数" : "不是素数");
            System.out.println((randomNumber.primeMC(n)) ? "是素数" : "不是素数");
        }


    }
}
